import java.util.EmptyStackException;
import java.util.Stack;

public class StackProblem {
	
	static class MinStack<T extends Comparable> {

		private Stack<T> minStack = new Stack<T>();
		private Stack<T> normalStack = new Stack<T>();

		public void push(T t) {
			T min = null;
			try {
				min = min();
			} catch(EmptyStackException e) {
			}
			if (min == null || (min != null && min.compareTo(t) > 0)) {
				min = t;
			}
			
			minStack.push(min);
			normalStack.push(t);
		}

		public T pop() {
			minStack.pop();
			return normalStack.pop();
		}

		public T min() {
			return minStack.peek();
		}


	}

	/**
	 * Q226: Design a data structure that supports push(), pop(), and min() all
	 * in O(1) timeDesign a data structure that supports push(), pop(), and
	 * min() all in O(1) time tags: google software programming algorithm
	 */

	public static void main(String[] args) {

		MinStack<Integer> minStack = new MinStack<Integer>();
		
		minStack.push(5);
		minStack.push(1);
		minStack.push(90);
		
		System.out.println("min " + minStack.min());
		System.out.println("pop " + minStack.pop());
		System.out.println("min " + minStack.min());
		System.out.println("pop " + minStack.pop());
		minStack.push(31);
		System.out.println("min " + minStack.min());
		System.out.println("pop " + minStack.pop());
		
	}
}
